1.6 How is the AST Gradually Constructed？

Now we know that the AST is constructed by the ParserASTListener. So, how does the ParserASTListener actually construct the AST? The ParserASTListener has a base class called AbstractParserAstListener, and they work together to complete the task:

Firstly, the AbstractParserAstListener is specifically used to respond to events. For each type of event, the AbstractParserAstListener creates a corresponding class, and these classes share a common parent class, ParserAstNode. For example:

@override
void beginBlock(Token token, BlockKind blockKind) {
  BlockBegin data =
      new BlockBegin(ParserAstType.BEGIN, token: token, blockKind: blockKind);
  seen(data);
}

@override
void endBlock(
    int count, Token beginToken, Token endToken, BlockKind blockKind) {
  BlockEnd data = new BlockEnd(ParserAstType.END,
      count: count,
      beginToken: beginToken,
      endToken: endToken,
      blockKind: blockKind);
  seen(data);
}

These are two methods in the AbstractParserAstListener, responding to the opening and closing events of code blocks. In each case, corresponding class instances, BlockBegin and BlockEnd (both inheriting from ParserAstNode), are created and then the seen method is called.

As mentioned in the second section, the Listener has many methods, and the AbstractParserAstListener implements each of them. They all follow the same pattern: first, creating an instance of the corresponding class, and then calling the seen method.

The ParserASTListener is specifically responsible for implementing the seen method. The seen method is where the construction of the syntax tree takes place. Let me describe the process of syntax tree construction in words.

First, in the ParserASTListener, there is a data attribute, which acts like a workspace. Instances of various ParserAstNode subclasses are added here. Its definition is as follows:

List<ParserAstNode> data = [];

All ParserAstNode types mainly fall into three categories, as defined by the ParserAstType enumeration:

• BEGIN: Indicates the start of a syntax element, such as BlockBegin.
• END: Indicates the end of a syntax element, such as BlockEnd.
• HANDLE: Represents the content of a syntax element.

In the AbstractParserAstListener, all events call the seen method. In the seen method, if the ParserAstNode passed in is of the BEGIN or HANDLE type, it is added to the data list.

For END type events, the seen method performs special operations:

• First, it backtracks along the data list to see if there is a corresponding BEGIN. If it doesn't match, it indicates a problem and throws an exception.
• If a corresponding BEGIN is found, it removes the BEGIN node and all its child nodes from the data list and adds them to the children field of the entry (the end node).

During this process, the nodes from BEGIN to END are added to the children of the END node and then removed from the data list. After that, the END node is inserted into the data list.

The data list acts as a temporary storage area. Some nodes are not top-level nodes and are located deep within the syntax tree. The parsing order of the Parser always satisfies their BEGIN, HANDLE, END sequence. Therefore, such a node can retrieve its portion from the global data and set the parent of these nodes to itself.

Ultimately, when the syntax tree parsing is completed, the data list returns to a calm state, leaving only one node, CompilationUnitEnd.

本文作者：Maeiee

本文链接：1.6 How is the AST Gradually Constructed？

版权声明：如无特别声明，本文即为原创文章，版权归 Maeiee 所有，未经允许不得转载！

喜欢我文章的朋友请随缘打赏，鼓励我创作更多更好的作品！